package pers.qianyu.month_202012.date_20201220;

import org.junit.*;

/**
 * 快速幂算法
 *
 * @author mizzle rain
 * @date 2020-12-20 22:35
 */
public class MyPow {
    // 递归形式
    private int pow2(int a, int b) {
        if (b == 0) {
            return 1;
        }
        if ((b & 1) == 1) {
            // 奇数
            return a * pow(a, b - 1);
        } else {
            b >>= 1;
            return pow(a, b) * pow(a, b);
        }
    }

    // 遍历形式
    private int pow(int a, int b) {
        if (b == 0) {
            return 1;
        }
        int res = 1;
        while (b != 0) {
            if ((b & 1) == 1) {
                res *= a;
            }
            a *= a;
            b >>= 1;
        }
        return res;
    }

    @Test
    public void test1() {
        int a = 2, b = 8;
        int result = new MyPow().pow(a, b);
        Assert.assertEquals(result, (int) Math.pow(a, b));
    }

    @Test
    public void test2() {
        int a = 4, b = 0;
        int result = new MyPow().pow(a, b);
        Assert.assertEquals(result, (int) Math.pow(a, b));
    }

    @Test
    public void test3() {
        int a = 5, b = 9;
        int result = new MyPow().pow(a, b);
        Assert.assertEquals(result, (int) Math.pow(a, b));
    }
}
